package algorithms.question.class05;

/**
 * leetcode 72阉割版，插入删除替换代价都是1
 * 经典中的经典
 * 编辑距离问题
 * 给定两个字符串s1,s2，怎么编辑能使s1变成s2
 * 保留d1、删除d2、添加d3、替换d4都是有代价的，可能一样可能不一样
 * 比如s1=abcd s2=abce
 * 第一种：直接由d替换成e 总代价：d4
 * 第二种：删除d再添加e 总代价：d2+d3
 * 求哪种代价最小
 *
 * @author guichang
 * @date 2021/8/1
 */

public class Code3_编辑距离 {
    // dp[i][j] i=str1.length() j=str2.length()
    // str1取前i个字符编辑成str2的前j个字符最小代价
    // 情况1 str1前i-1个字符变成str2的前j个字符，删除str1的第i个字符
    // 情况2 str1的前i个字符变成str2的前j-1个字符，str1增加str2的第j个字符
    // 情况3 str1的第i个字符与str2的第j个字符相等，只需要将str1的前i-1变成str2的前j-1个字符即可
    // 情况4 str1的第i个字符与str2的第j个字符不等，先将str1的前i-1变成str2的前j-1个字符，再将str1的第i个字符变成str2的第j个字符
}